package org.zlb.algorithm.sort;

/**
 * 希尔排序（插入排序）
 *
 * @author zhoulingbo
 * @date 2021/7/9 17:14
 */
public class ShellSort extends AbstractSort {

    @Override
    public void sort(int[] arr) {
        int gap = arr.length / 2;
        while (gap > 0) {
            for (int i = 0; i <= gap - 1; i ++) {
                for (int j = i + gap; j <= arr.length - 1; j += gap) {
                    if (compare(arr[j], arr[j-gap]) < 0) {
                        swap(arr, j, j-gap);
                    }
                }
            }
            gap = gap / 2;
        }
    }
}
